package cn.lishiyuan.algorithm.sort;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;


/**
 * 桶排序
 * <br>
 * 桶排序的思路是将数据划分到有序的不同的桶只中，每个桶单独进行排序，最后依次读取桶之中的数据就是有序的
 */
public class BucketSort {

    /**
     *
     * @param data
     * @param map 映射到bucket的index
     * @return
     * @param <T>
     */
    public <T extends Comparable<T>> List<T> sort(List<T> data,Function<T,Integer> map) {
        List<List<T>> buckets = new ArrayList<>();
        LeeSort sort = new MergeSort();

        // 对每个函数映射到桶
        for (T datum : data) {
            Integer bucketIndex = map.apply(datum);
            while (buckets.size() <= bucketIndex) {
                buckets.add(new ArrayList<>());
            }
            List<T> nowList = buckets.get(bucketIndex);
            if (nowList == null) {
                nowList = new ArrayList<>();
                buckets.set(bucketIndex,nowList);
            }
            nowList.add(datum);
        }

        // 对每个桶进行排序
        for (List<T> bucket : buckets) {
            // 排序
            sort.sort(bucket);
        }

        // 合并所有桶
        List<T> list = buckets.stream().flatMap(List::stream).toList();

        return list;
    }
}
